package nowcoder;

import java.util.ArrayList;

public class PathWithSpecificSum {
	
	public static void main(String[] args) {
		TreeNode root = new TreeNode(10);
		TreeNode node1 = new TreeNode(5);
		TreeNode node2 = new TreeNode(12);
		TreeNode node3 = new TreeNode(4);
		TreeNode node4 = new TreeNode(7);
		
		root.left = node1;
		root.right = node2;
		node1.left = node3;
		node1.right = node4;
		
		System.out.println(findPath(root, 15));
	}
	
	public static ArrayList<ArrayList<Integer>> findPath(TreeNode root,int target) {
		ArrayList<ArrayList<Integer>> res = new ArrayList<>();
		
		if(root == null)
			return res;
		
		int sum = 0;
		ArrayList<Integer> single = new ArrayList<>();
		findPathRecursive(root, res, single, sum, target);
		
		res.sort((ArrayList<Integer> list1, ArrayList<Integer> list2) -> list2.size() - list1.size());
		
		return res;
	}

	private static void findPathRecursive(TreeNode node, ArrayList<ArrayList<Integer>> res, ArrayList<Integer> single, int sum,
			int target) {
		sum += node.val;
		single.add(node.val);
		
		if(sum == target && node.left == null && node.right == null) {
			res.add(new ArrayList<>(single));
			return;
		}
		
		if(sum > target)
			return;
		
		if(node.left != null) { 
			findPathRecursive(node.left, res, single, sum, target);
			single.remove(single.size() - 1);
		}
		
		if(node.right != null) {
			findPathRecursive(node.right, res, single, sum, target);
			single.remove(single.size() - 1);
		}
	}

}
